package com.code.test.first.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.md
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1：
 * <p>
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为： [ [7], [2,2,3] ]
 * 示例 2：
 * <p>
 * 输入：candidates = [2,3,5], target = 8,
 * 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
 */
public class Code39 {

    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 7};
        List<List<Integer>> ret = combine(nums, 7);
        System.out.println(ret);
    }

    static List<List<Integer>> ret = new ArrayList<>();
    static LinkedList<Integer> path = new LinkedList<>();

    public static List<List<Integer>> combine(int[] nums, int targetSum) {
        backtracking(nums, targetSum, 0, 0);
        return ret;
    }

    public static void backtracking(int[] nums, int targetSum, int sum, int idx) {

        if (sum == targetSum) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < nums.length; i++) {
            int cur = nums[i];
            if (sum + nums[i] > targetSum) {
                //总和大于就回去
                break;
            }
            path.add(cur);
            //可以重复读取当前的数,
            backtracking(nums, targetSum, sum + cur, i);
            path.removeLast();
        }
    }

}
